One of the most important requirements for today's high-performance forwarding engines of Internet is the ability to identify the packets that belong to a certain flow (a flow is defined by some rule; a collection of rules is called a classifier) and apply an action necessary to satisfy an increasing set of service requirements. Identification of the flow of an incoming packet is termed packet classification.
Packet classification is a critical function of switches, routers and firewalls. Typical applications include access control list of firewalls, flow tables of SDN routers/switches, packet classifier of QoS routing and so on. A packet classifier is designed to compare a number of header fields of an incoming packet against a set of rules and determine an action from matched rules. Sample actions include forwarding the packet, rejecting the packet, routing the packet to a particular application, etc. The packet classifier searches the rules to find the highest priority one matching the incoming packet.
The most common used solution in commercial products for packet classification is based on TCAM (Ternary Content Addressable Memory), which relies on hardware to process a packet in one clock cycle. However, it is inflexible and power hungry, and is reaching the capacity limit of the technology.
Therefore, the industry is seeking algorithmic solutions instead. In recent years, many algorithms have been proposed for packet classification, such as HiCuts, HyperCuts, HyperSplit, RFC and HSM.
However, the size of rule set grows rapidly with the exploding of Internet applications. For large rule sets, existing algorithms are generally based on decomposition or decision-tree, which faces a large amount of rule replication. Moreover, the memory consumption and construction time grows rapidly with the size of rule set, which significantly reduces the scalability performance. The method presented in this disclosure is called Split, Compression and Intersection (SCI).
Throughout the drawings, identical reference numbers designate similar, but not necessarily identical, elements.